翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

block graph : ウィキペディア英語版
block graph

In graph theory, a branch of combinatorial mathematics, a block graph or clique tree〔.〕
is a type of undirected graph in which every biconnected component (block) is a clique.
Block graphs are sometimes erroneously called Husimi trees (after Kôdi Husimi),〔 but that name more properly refers to cactus graphs, graphs in which every nontrivial biconnected component is a cycle.〔See, e.g., , a 1983 review by Robert E. Jamison of another paper referring to block graphs as Husimi trees; Jamison attributes the mistake to an error in a book by Behzad and Chartrand.〕
Block graphs may be characterized as the intersection graphs of the blocks of arbitrary undirected graphs.〔.〕
==Characterization==
Block graphs are exactly the graphs for which, for every four vertices ''u'', ''v'', ''x'', and ''y'', the largest two of the three distances ''d''(''u'',''v'') + ''d''(''x'',''y''),
''d''(''u'',''x'') + ''d''(''v'',''y''),
and ''d''(''u'',''y'') + ''d''(''v'',''x'') are always equal.〔.〕〔.〕
They also have a forbidden graph characterization as the graphs that do not have the diamond graph or a cycle of four or more vertices as an induced subgraph; that is, they are the diamond-free chordal graphs.〔 They are also the Ptolemaic graphs (chordal distance-hereditary graphs) in which every two nodes at distance two from each other are connected by a unique shortest path,〔 and the chordal graphs in which every two maximal cliques have at most one vertex in common.〔
A graph ''G'' is a block graph if and only if the intersection of every two connected subsets of vertices of ''G'' is empty or connected. Therefore, the connected subsets of vertices in a connected block graph form a convex geometry, a property that is not true of any graphs that are not block graphs.〔.〕 Because of this property, in a connected block graph, every set of vertices has a unique minimal connected superset, its closure in the convex geometry. The connected block graphs are exactly the graphs in which there is a unique induced path connecting every pair of vertices.〔

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「block graph」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.